#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    vector<int> smallerNumbersThanCurrent(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> res;
        for (int i = 0; i < n; i++)
        {
            int ans = 0;
            for (int j = 0; j < n; j++)
            {
                // cout << nums[j] << " " << nums[i] << endl;
                if (nums[j] < nums[i])
                    ans++;
            }
            res.push_back(ans);
        }
        return res;
    }

    vector<int> smallerNumbersThanCurrent_2(vector<int> &nums)
    {
        vector<pair<int, int>> data;
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            data.emplace_back(nums[i], i);
        }
        sort(data.begin(), data.end());

        vector<int> ret(n, 0);
        int prev = -1;
        for (int i = 0; i < n; i++)
        {
            if (prev == -1 || data[i].first != data[i - 1].first)
            {
                prev = i;
            }
            ret[data[i].second] = prev;
        }
        return ret;
    }

    vector<int> smallerNumbersThanCurrent_3(vector<int> &nums)
    {
        vector<int> cnt(101, 0);
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            cnt[nums[i]]++;
        }
        for (int i = 1; i <= 100; i++)
        {
            cnt[i] += cnt[i - 1];
        }
        vector<int> ret;
        for (int i = 0; i < n; i++)
        {
            ret.push_back(nums[i] == 0 ? 0 : cnt[nums[i] - 1]);
        }
        return ret;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {8, 1, 2, 2, 3};
    vector<int> ans = s.smallerNumbersThanCurrent(nums);
    for (int a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
